package szte.objectorgy.collections;

/**
 * Set data structure with a red-black tree underlying implementation.
 * 
 * @author Endre PALATINUS
 * @param <T>
 *            The type of the elements stored in this collection.
 */
public class TreeSet<T extends Comparable<T>> implements Set<T> {

	/** Internal storage for the elements of the set. */
	private TreeMap<T, Boolean> map;
	
	public TreeSet() {
		map = new TreeMap<T, Boolean>();
	}

	@Override
	public void add(T element) {
		map.put(element, null);
	}

	@Override
	public void addAll(Collection<T> collection) {
		Iterator<T> it = collection.getIterator();
		while (it.hasNext()) {
			map.put(it.next(), null);
		}
	}

	@Override
	public void clear() {
		map.clear();
	}

	@Override
	public boolean contains(T element) {
		return map.containsKey(element);
	}

	@Override
	public boolean isEmpty() {
		return map.isEmpty();
	}

	/**
	 * Iterator for the inorder tree traversal of a TreeSet.
	 * 
	 * @author Endre PALATINUS
	 */
	private class TreeSetIterator implements Iterator<T> {

		TreeMap<T, Boolean>.TreeMapIterator mapIter;

		public TreeSetIterator() {
			mapIter = map.getIterator();
		}

		@Override
		public boolean hasNext() {
			return mapIter.hasNext();
		}

		@Override
		public T next() {
			return mapIter.next().getKey();
		}
	}

	@Override
	public Iterator<T> getIterator() {
		return new TreeSetIterator();
	}

	@Override
	public void remove(T element) {
		map.remove(element);
	}

	@Override
	public void removeAll(Collection<T> collection) {
		Iterator<T> it = collection.getIterator();
		while (it.hasNext()) {
			remove(it.next());
		}
	}

	@Override
	public int size() {
		return map.size();
	}

	@Override
	public Object[] toArray() {
		Object[] obj = new Object[size()];
		int position = 0;
		Iterator<T> it = getIterator();
		while (it.hasNext()) {
			obj[position++] = it.next();
		}

		return obj;
	}
	
	public String toString() {
		return map.toString();		
	}
}
